/**
 * LeetCode144：二叉树的前序遍历
 * 给定一个二叉树，返回它的前序遍历
 * 使用迭代算法（通过栈来实现）
 * function TreeNode(val){
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var preOrder = function (root){
    const res = [];
    const stack =[];
    //根节点不为空时压入栈
    if (root)stack.push(root);
    while (stack.length){
        const n = stack.pop();
        res.push(n.val);
        if (n.right) stack.push(n.right);
        if (n.left) stack.push(n.left);
    }
    return res;
}

//时间复杂度：O(n)
//空间复杂度：O(n)